題目

• Ugly Number的定義
  • 因子有2、3、5的數字。
  • 1被認為是Ugly Number
• 寫一個function nthUglyNumber(int n)，返回第n個ugly number.
  • n <= 1690

*** 解法***

• 使用動態規劃法，建立由小到大的ugly number並依序儲存，直到建立到n為止(後面就不需要了，因為已經能回傳答案)
• 已知 n不超過1690，那我們直接建一個大小為1691的array稱作ugly，並將ugly[0]填1，因為題目說到1是ugly number。
• 之後宣告3個變數i2,i3,i5，初始都在0。
• for loop過程比較ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5，哪個最小，此ugly[i]就儲存它，並將對應的變數(i2,i3,i5)+1。
  • 這樣做i2,i3,i5，會輪流前進，並且經過曾經乘完結果的數字，用那些數子做再繼續乘與比較，得到ugly[i]
    • i=1,i2=0,i3=0,i5=0 -> ugly=[1,2,0,...,0]
    • i=2,i2=1,i3=0,i5=0 -> ugly=[1,2,3,0,...,0],
    • i=3,i2=1,i3=1,i5=0 -> ugly=[1,2,3,4,...,0], i2=1,經過上個結果。
    • i=4,i2=2,i3=1,i5=0 -> ugly=[1,2,3,4,5,0,...,0]
    • ...

Code

class Solution {
public:
    int nthUglyNumber(int n) {
        int ugly[1691]={[0] = 1};
        
        int i2 = 0, i3 = 0, i5 = 0;
        for(int i = 1; i < n; i++){
            ugly[i] = min(min(ugly[i2] * 2, ugly[i3] * 3), ugly[i5] * 5);
            if(ugly[i] == ugly[i2] * 2){
               i2++;
            }
            if(ugly[i] == ugly[i3] * 3){
               i3++;
            }
            if(ugly[i] == ugly[i5] * 5){
               i5++;
            }
            cout <<ugly[i]<<" ";
        }
        return ugly[n - 1];
    }
};